#pragma once

#include <iostream>
#include <assert.h>

template <typename T>
class List
{
public:
    struct Node
    {
        T data = 1;
        Node *pre = nullptr;
        Node *next = nullptr;

        Node(T dt) : data(dt), pre(nullptr), next(nullptr) {}
        Node(T dt, Node *pre, Node *next) : data(dt), pre(pre), next(next) {}
    };

    class Iter
    {
    public:
        explicit Iter(Node *node = nullptr): ptr_(node){}
        Iter &operator++()
        {
            ptr_ = ptr_->next;
            return *this;
        }

        Iter operator++(int)
        {
            Iter tmp = *this;
            ptr_ = ptr_->next;
            return tmp;
        }

        bool operator!=(const Iter &rhs)
        {
            return rhs.ptr_ != ptr_;
        }

        bool operator==(const Iter &rhs)
        {
            return rhs.ptr_ == ptr_;
        }

        T operator*()
        {
            return ptr_->data;
        }

    public:
        Node *ptr_;
    };

public:
    List();
    List(const List &list) = delete;
    List(List &&list);

    void push_back(T data) const;
    void push_front(T data) const;

    T front() const;
    T back() const;

    Iter end();
    Iter begin();

    bool empty() const;

private:
    Node *head_;
    Node *end_;
};

template <typename T>
using NodeT = typename List<T>::Node;

template <typename T>
List<T>::List()
{
    head_ = new Node(0);
    end_ = new Node(-1, head_, head_);
    head_->next = end_;
    head_->pre = end_;
}

template <typename T>
List<T>::List(List<T> &&list)
{
    if (this == &list)
        return;

    this->head_ = list.head_;
    this->end_ = list.end_;
    list.head_ = nullptr;
    list.end_ = nullptr;
}

template <typename T>
void List<T>::push_back(T data) const
{
    NodeT<T> *node = new NodeT<T>(data);
    NodeT<T> *pre = end_->pre;
    pre->next = node;

    node->next = end_;
    node->pre = pre;

    end_->pre = node;
}

template <typename T>
void List<T>::push_front(T data) const
{
    NodeT<T> *node = new NodeT<T>(data);
    NodeT<T> *next = head_->next;
    head_->next = node;

    node->next = next;
    node->pre = head_;

    next->pre = node;
}

template <typename T>
T List<T>::front() const
{
    assert(!empty());
    return head_->next->data;
}

template <typename T>
T List<T>::back() const
{
    assert(!empty());
    return end_->pre->data;
}

template <typename T>
bool List<T>::empty() const
{
    return head_->next == end_;
}

template <typename T>
typename List<T>::Iter List<T>::end()
{
    return Iter(end_);
}

template <typename T>
typename List<T>::Iter List<T>::begin()
{
    return Iter(head_->next);
}